perm filename A06.TEX[257,RWF] blob sn#847484 filedate 1987-10-26 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00027 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\def\fnc#1{\mathop{\rm #1}\nolimits}
\def\ld{\mathrel{\hbox{$<$\kern-4pt$\cdot$}}}
\def\gd{\mathrel{\hbox{$\cdot$\kern-4pt$>$}}}
\rm
\line{\sevenrm a06.tex[257,phy] \today\hfill}


\def\boxb{\boxbinarya{$\scriptstyle a$}}
\def\boxbb{\boxbinarya{$\scriptstyle b$}}
\def\boxbbb{\boxbinarya{$\scriptstyle c$}}

\bigskip
Let $\langle x,y\rangle$ be a fixed one-to-one
(``pairing'') function in {\bf R}$↓2$
from $N\times N$ onto~$N↑+$, and $\alpha$ and~$\beta$ the corresponding
inverse functions such that $\langle x,y\rangle↓{\alpha}=x$,
$\langle x,y\rangle↓{\beta}=y$. Then $n$-tuples can be represented uniquely
{\sl a la\/} LISP:
$$\eqalignno{&[\ ]=0\cr
&[x]=\langle x,0\rangle\cr
&[x↓1,x↓2]=\langle x↓1,\langle x↓2,0\rangle\rangle =\langle x↓1,[x↓2]\rangle\cr
&[x↓1,x↓2,x↓3]=\langle x↓1,\langle x↓2,\langle x↓3,0\rangle\rangle\rangle
=\langle x↓1,[x↓2,x↓3]\rangle\quad\hbox{etc.}\cr
&[x↓1,x↓2,\ldots]↓{\alpha}=x↓1\cr
&[x↓1,x↓2,\ldots]↓{\beta\alpha}=x↓2\cr
&[x↓1,x↓2,x↓3,\ldots]↓{\beta\beta\alpha}=x↓3\cr
&[x↓1,x↓2,x↓3,\ldots]↓{\beta↑{n-1}\alpha}=x↓n\cr
&[x↓1,x↓2,x↓3,\ldots]↓{\beta}=[x↓2,x↓3,\ldots]\cr
&[x↓1,x↓2,x↓3,\ldots]↓{\beta\beta}=[x↓3,x↓4,\ldots]\,,\quad\hbox{etc.}\cr
\noalign{\hbox{An additional convention is sometimes useful:}}
&[x↓1.x↓2]=\langle x↓1,x↓2\rangle\cr
&[x↓1,x↓2.x↓3]=\langle x↓1,\langle x↓2,x↓3\rangle\rangle\cr
&[x↓1,x↓2,x↓3.x↓4]=\langle x↓1,\langle x↓2,\langle x↓3,x↓4\rangle\rangle\rangle
\quad\hbox{etc.}\cr}$$

\bigskip
Let $\{\phi↓i\}$ be, in Rogers' sense, an acceptable enumeration of the
partial recursive functions of one variable, ${\bf P}↓1$. That is, the
enumeration satisfies these axioms:

\smallskip
\disleft 20pt:(1):
(Universal function.) There is a function $U\in{\bf P}↓2$ such that 
$\phi↓i(x)≡U(i,x)$.

\smallskip
\disleft 20pt:(2):
(S-M-N Theorem.) There is a function $\sigma\in{\bf R}↓2$ such that
$$\phi↓i(\langle x,y\rangle)=\phi↓{\sigma(i,x)}(y)\,.$$

\smallskip
\disleft 20pt:(3):
(Church's hypothesis.) If it is possible to construct an algorithm in
the ordinary sense of the word to compute $f(x)$, then it is possible
to obtain an index~$i$ such that
$$\phi↓i(x)=f(x)\,.$$
When we use Church's hypothesis (CH), we will put a square around the first
occurrence of the index obtained. For example, there is an obvious
algorithm which, when applied to $[x,y]$, gives $[y,x]$; if
$z=[x,y]$, $z↓{\alpha}=x$, $z↓{\beta\alpha}=y$,
$\langle z↓{\alpha},0\rangle=[x]$, and $\langle z↓{\beta\alpha},[x]\rangle
=[y,x]$. By~CH,
$$\phi↓{\boxb}([x,y])≡[y,x]$$
for a certain obtainable $a$, and for all $x$ and~$y$. Conventionally,
we will use early letters ($a$--$e$)  for indices obtained by~CH, and
letters $i$--$m$ for given or variable indices.

To have a systematic way of talking about $n$-ary partial recursive functions
for each~$n$, and even about functions with a variable number of arguments,
we define:
$$\psi↓i(x↓1,x↓2,\ldots,x↓n)=\phi↓i([x↓1,x↓2,\ldots,x↓n])\,.$$
[RWF: Use $\mu$ instead of $\psi$?]
In particular,
$$\psi↓i(x)≡\phi↓i([x])≡\phi↓i(\langle x,0\rangle)
≡U(i,\langle x,0\rangle)≡\phi↓{\boxb}(i,x)
≡\phi↓{\sigma(a,i)}(x)$$
so there is an effective mapping from $\psi$-indices to $\phi$-indices for
functions of one argument.
$$\eqalign{\psi↓i(x,y)&=\phi↓i([x,y])=\phi↓{\sigma(i,x)}([y])
=\psi↓{\sigma(i,x)}(y)=\psi↓{\sigma\bigl(\sigma(i,x),y\bigr)}(\;)\cr
\psi↓i(x,y,z)&=\psi↓{\sigma(\sigma(i,x),y)}(z)\,,\quad\hbox{etc.}\cr}$$
By convention,
$$\psi↓i(\;)=\phi↓i([\;])=\phi↓i(0)\,.$$
We abbreviate subscripts involving $\sigma$ by writing, say,
$\psi↓{i,x,y}$ for $\psi↓{\sigma(\sigma(i,x),y)}$. We may
also write 
$$\eqalign{\sigma↓1(i,x)&=\sigma(i,x)\,,\cr
\sigma↓2(i,x,y)&=\sigma\bigl(\sigma(i,x),y\bigr)\,,\cr
\sigma↓3(i,x,y,z)&=\sigma\bigl(\sigma\bigl(\sigma(i,x),y\bigr),z\bigr)\,,\quad
\hbox{etc.}\cr}$$

Church's hypothesis may be extended to the $\psi$-enumeration. If it is
possible to construct an algorithm in the ordinary sense of the word
to compute $f(x↓1,x↓2,\ldots,x↓n)$, we may replace the occurrences of~$x↓1$
with~$z↓{\alpha}$, $x↓2$ with~$z↓{\beta\alpha}$, etc., to get an
algorithm which computes a function $g(z)=f(z↓{\alpha},z↓{\beta\alpha},
z↓{\beta\beta\alpha},\ldots)$. Let $\phi↓{\boxb}(z)=g(z)$.
Then $\psi↓a(x↓1,x↓2,\ldots,x↓n)=\phi↓a([x↓1,x↓2,\ldots,x↓n])=
g([x↓1,x↓2,\ldots,x↓n])=f(x↓1,x↓2,\ldots,x↓n)$, and $a$~is the
desired index for~$f$ in the $\psi$-enumeration. When we use this
derived form of Church's hypothesis, we will again enclose~$a$ by a square
in its first use:
$$\psi↓{\;\boxb\;}(x↓1,x↓2,\ldots,x↓n)=f(x↓1,x↓2,\ldots,x↓n)\,.$$

\proclaim
%\medskip\noindent
Theorem. Composition in $\{\phi↓i\}$ is effective.

\noindent
That is, there is a function ${\rm comp}\,\in{\bf R}↓2$ such that
$$\phi↓{{\rm comp}(i,j)}(x)=\phi↓i\bigl(\phi↓j(x)\bigr)\,.$$
\par

%\medskip
Define $\phi↓{\boxb}(z)=
U\bigl(z↓{\alpha},U(z↓{\beta\alpha},z↓{\beta\beta})\bigr)$.
Then, if $z$ is of the form $[i,j.x]$,
$$\phi↓{a,i,j}(x)=\phi↓{a,i}([j.x])=\phi↓a([i,j.x])
=U\bigl(i,U(j,x)\bigr)=\phi↓i\bigl(\phi↓j(x)\bigr)\,,$$
and ${\rm comp}(i,j)=\sigma\bigl(\sigma(a,i),j\bigr)$ is the required
function. Define $\psi↓{\,\boxbb\,}(a,i,j)=\sigma\bigl(\sigma(a,i),j\bigr)$;
then $\psi↓{b,a}(i,j)={\rm comp}(i,j)$, so $\sigma(b,a)$ gives the
$\psi$-index of comp if desired.

\proclaim
%\medskip\noindent
Theorem.  Composition in $\{\psi↓i\}$ is effective.
That is, there is a function ${\rm comp}1\in {\bf R}↓2$ such that
$$\psi↓{{\rm comp}1(i,j)}(x)=\psi↓i\bigl(\psi↓j(x)\bigr)\,.$$
\par

%\medskip
Define $\psi↓{\,\boxb\,}(i,j,x)=U\bigl(i,\bigl[U(j,[x])\bigr]\bigr)$.
Then $\psi↓{a,i,j}(x)=\psi↓i\bigl(\psi↓j(x)\bigr)$, and, as required,\break
${\rm comp}1(i,j)=\sigma\bigl(\sigma(a,i),j\bigr)$.
Define $\psi↓{\;\boxbb\;}(a,i,j)=\sigma\bigl(\sigma(a,i),j\bigr)$, so
$\sigma(b,a)$ gives the $\psi$-index of comp1 if desired.

\proclaim
%\medskip\noindent
Theorem.  Exchange of argument positions in $\psi$ is effective.
That is, there is a function ${\rm exch}\in{\bf R}↓1$ such that
$$\psi↓{{\rm exch}(i)}(x,y)=\psi↓i(y,x)\,.$$
\par

\noindent{\bf Proof.}
Define
$$\phi↓{\boxb}(z)=U\bigl(z↓{\alpha},[z↓{\beta\beta\alpha},z↓{\beta\alpha}])\,.$$
That is, if $z$ is of the form $[i,x,y]$,
$$\psi↓{a,i}(x,y)=\phi↓{a,i}([x,y])=\phi↓a([i,x,y])=
U(i,[y,x])=\phi↓i([y,x])=\psi↓i(y,x)\,,$$
so the desired function is ${\rm exch}(i)=\sigma(a,i)$.\xskip\blackslug

The logic of the previous proof can be made explicit. We wanted to get 
from~$i$ an index~$j$ such that $\psi↓j(x,y)=\psi↓i(y,x)$. Because
of the SMN~axiom, it suffices to find an index~$a$ such that
$\psi↓a(j,x,y)=\psi↓i(y,x)$. Replacing $\psi↓a$ and~$\psi↓i$ by their
definitions, we find we need
$\phi↓a([j,x,y])=\phi↓i([y,x])=U(i,[y,x])$. Letting $j=i$, an
application of~CH finishes the job.

\proclaim
The Constructive Recursion Lemma.
An index $a$ can be constructively obtained from a $\psi$-index for 
$f\in {\bf P}↓2$, such that $\phi↓a(x)=f(a,x)$.
\par

\noindent
{\bf Proof.} Let $\phi↓{\,\boxbb\,}(\langle i,\langle y,x\rangle\rangle)
=\psi↓i\bigl(g(i,y),x\bigr)$; we shall shortly show what function~$g$ should~be.
The intent is that $i$ be an index for~$f$, and that setting $y=b$ results
in $g(i,y)=a$. Then
$$\phi↓{\sigma↓2(b,i,b)}(x)=\psi↓i\bigl(g(i,b),x\bigr)\,.$$
If $g(i,y)≡\sigma↓2(y,i,y)$, letting $a=\sigma↓2(b,i,b)$ gives
$$\eqalign{\phi↓a(x)&=\psi↓i\bigl(g(i,b),x\bigr)=\psi↓i\bigl(\sigma↓2(b,i,b),x
\bigr)\cr
&=\psi↓i(a,x)\,,\cr}$$
as desired.\xskip\blackslug

%{\rmn
%{\narrower\smallskip\noindent
\smallskip\noindent
{\bf Exercise:} Could we have defined $\psi↓{\,\boxbb\,}(\langle y,\langle
i,x\rangle\rangle)=\psi↓i\bigl(g(i,y),x\bigr)$?
%\smallskip}
%}

%{\rmn
%{\narrower\smallskip\noindent
\smallskip\noindent
{\bf Exercise:} Prove the analogous lemma to get $\psi↓a(x)=f(a,x)$.
%\smallskip}
%}

\proclaim
The Recursion Theorem.
If $f\in {\bf R}↓1$, there is an index $a$ such that $\phi↓{f(a)}≡\phi↓a$.
\par

\noindent
{\bf Proof.} Program $a$ can simulate program $f(a)$ by constructing a
copy of itself, applying $f$ to that copy, and using the universal function.
\xskip\blackslug

By the recursion lemma, we can construct $a$ effectively from an index
for~$f$, such that
$$\phi↓a(x)=U\bigl(f(a),x\bigr)=\phi↓{f(a)}(x)\,.$$
The recursion theorem is a fixed point theorem; it says that any algorithm
that transforms programs changes some program into an equivalent one.

\vfill\eject

%\medskip
\line{\bf Recursive Definition.\hfill}

Suppose we define $f(x)=g\bigl(f(h↓1(x)),f(h↓2(x))\bigr)$ recursively,
in terms of partial recursive functions~$g$, $h↓1$, and~$h↓2$. We want
to show how, by applying CH and the recursion theorem, we can get a~$\phi$-index
for~$f$. We want an index~$a$ satisfying
$$\eqalign{\phi↓a(x)&=g\bigl(\phi↓a(h↓1(x)),\phi↓a(h↓2(x))\bigr)\cr
&=g\bigl(U(a,h↓1(x)),U(a,h↓2(x))\bigr)\cr
&=p(a,x)\,,\cr}$$
readily obtained by the recursion lemma. In fact, $a$~is uniformly obtained
from indices for~$g$, $h↓1$, and~$h↓2$. This shows that any acceptable
programming system permits implementation of recursive definitions.

%{\rmn
%{\narrower\smallskip\noindent
\smallskip\noindent
({\bf Exercise:} What about mutually recursive definitions?)
%\smallskip}
%}

\smallskip
Notice that the implementation of recursion embodied above works by having
the program make a copy of itself for each recursion, and interpretively
execute that copy, which may in turn make copies of itself.

%\vfill\eject

%\line{\sevenrm a03.tex[257,phy] \today\hfill}

\bigskip
\noindent{\bf The Operator Recursion Lemma}

A program family is a recursive infinite sequence of programs ($\phi$-indices),
say $p(1),p(2),\ldots\,$; the $i↑{\rm th}$ program of the family computes
$\phi↓{p(i)}(x)=U\bigl(p(i),x\bigr)$. Given an arbitrary $f\in{\bf P}↓2$,
$\phi↓{\boxb}(\langle i,x\rangle)=f(i,x)$,
$\phi↓{\sigma(a,i)}(x)=f(i,x)$, so $\sigma(a,1),\sigma(a,2),\ldots$ 
is a program family to compute $f(1,x),f(2,x),\ldots\,$. We call $a$
the {\it family index\/} of such a family, and $i$ the {\it ordinal\/} of
$\sigma(a,i)$ in the family. By taking $f(i,x)=U\bigl(p(i),x\bigr)$,
we find for any program family an equivalent family derived from a family
index.

Let $h(k,j,x)$ be an arbitrary member of ${\bf P}↓3$. In particular,
$h$~may treat $k$ as a family index, and $k$ as an ordinal. It may construct,
for any~$n$, the $n↑{\rm th}$ program $\sigma(k,n)$ in the family,
and the program $\sigma(k,j)$ of ordinal~$j$. It may apply such a program
to an arbitrary argument~$y$, using $U\bigl(\sigma(k,n),y\bigr)$.
By CH, $\phi↓{\boxbb}(\langle k,\langle j,x\rangle\rangle)=h(k,j,x)
=\phi↓{\sigma(b,k)}(\langle j,x\rangle)$. For any~$k$, $\sigma(b,k)$
is a family index, with $\sigma\bigl(\sigma(b,k),j\bigr)$ the $j↑{\rm th}$
member. By the recursion lemma, 
$$\phi↓{\boxbbb}(x)=\phi↓{\sigma(b,)}(x)\quad\hbox{for all $x$}.$$
For all $i$ and $x$,
$$\phi↓{\sigma(c,i)}(x)=\phi↓c(\langle i,x\rangle)=\phi↓{\sigma(b,c)}
(\langle i,x\rangle)=\phi↓b(\langle c,\langle i,x\rangle\rangle)=h(c,i,x)\,.$$
We have exhibited a family index $c$ for which the $i↑{\rm th}$ member of the
family gives the result $\phi↓{\sigma(c,i)}(x)$ of applying~$h$
to its family index~$c$, its ordinal~$i$, and its argument~$x$. Because
$\sigma(c,i)$ is its own $\phi$-index, this generalizes the recursion lemma.

\bigskip
\line{\bf The Padding Theorem\hfill}

Given a $\phi$-index $m$, we want to construct a family of distinct programs
all of which compute~$\phi↓m$. Use the ORL to construct a family of index~$a$,
where $\phi↓{\sigma(a,i)}$, on input~$x$, tests whether 
$\sigma(a,1),\sigma(a,2),\ldots,\sigma(a,x)$ are all distinct. If not,
the result is~$i$. If all are distinct, the result is $\phi↓m(x)$.

If for $j<k$, $\sigma(a,j)=\sigma(a,k)$, then $\phi↓{\sigma(a,j)}(k)=j$
but $\phi↓{\sigma(a,k)}(k)=k$, absurd. Therefore all members of family~$a$
are distinct, and each computes $\phi↓m(x)$. By enumeration of the family
members, one finds arbitrarily large~$n$ for which $\phi↓n=\phi↓m$


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd
First draft (not published) April 12, 1984.

\bye